수학적 귀납법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

수학적 귀납법은 페아노 공리계에서 정의되는 증명 방법으로, 1항 술어가 두 조건을 만족하면 임의의 자연수에 대해 성립함을 증명한다. 이 방법은 기본 사례와 귀납 단계를 통해 명제의 일반적인 성립을 보이며, 다양한 형태로 변형되어 사용된다. 수학적 귀납법은 자연수의 정렬성, 초한 귀납법 등과 동치 관계에 있으며, 부등식, 홀수의 합 공식 등을 증명하는 데 활용된다. 하지만, "모든 말은 같은 색이다"와 같은 오류가 발생할 수 있으며, 대머리 역설과 같은 모호한 개념에 적용하면 역설적인 결과를 초래할 수 있다.

더 읽어볼만한 페이지

귀납 - 마음
마음은 의식, 사고, 지각, 감정, 동기, 행동, 기억, 학습 등을 포괄하는 심리적 현상과 능력의 총체이며, 다양한 분야에서 연구되고 인간 삶의 중추적인 역할을 한다.
귀납 - 이론
이론은 특정 주제를 이해, 설명, 예측하기 위한 분석적 도구로, 논리적 원칙을 따르며, 과학에서는 관찰과 실험으로 확인된 사실에 기반한 자연 세계에 대한 설명으로, 반증 가능성을 지니고 학문 분야에서 지식 축적과 논리적 설명에 필수적인 역할을 한다.
증명 - 정리
정리는 논리학과 수학에서 공리를 바탕으로 증명된 참인 명제로서, "만약 A이면 B이다" 형태의 가정적 조건문으로 표현되며, 수학 외 다양한 분야에서도 사용되지만 수학에서의 엄밀한 증명과는 차이가 있다.
증명 - 가환 그림
가환 그림은 대상, 사상, 경로 또는 합성으로 이루어진 구조로, 대수학에서 사상의 종류를 화살표 기호로 나타내고 점선 화살표로 사상의 존재성을 표시하며, 부분 다각형 그림이 가환적일 때 전체 그림이 가환적이라고 정의되고, 범주론에서 함자로 해석되며 호몰로지 대수학에서 사상의 성질 증명에 활용된다.
수리논리학 - NAND 게이트
NAND 게이트는 모든 입력이 1일 때 0을 출력하고 그 외에는 1을 출력하는 논리 게이트로서, 다양한 기호로 표현되며, AND 연산의 결과를 부정하는 연산을 수행하고, 여러 방식으로 구현될 수 있으며, 기능적으로 완전하여 디지털 회로 설계에 필수적이다.
수리논리학 - 셈
셈은 대상의 개수를 파악하는 기본적인 행위로, 수학에서는 집합의 원소 개수를 파악하는 과정으로 정의되며, 셈의 방식에 따라 결과가 달라질 수 있고, 셈을 배우는 과정은 아동의 교육 및 발달에 중요한 역할을 한다.

수학적 귀납법
개요
이름	수학적 귀납법
로마자 표기	Suhakjeok Gwinabeop
영어 이름	Mathematical Induction
일본어 이름	数学的帰納法 (Sūgakuteki Kinōhō)
정의
설명	어떤 명제 P(n)이 모든 자연수 n에 대해 성립함을 증명하는 방법
기본 단계	n = 0 또는 n = 1일 때 P(n)이 성립함을 보이는 단계
귀납 단계	P(k)가 참이라고 가정할 때 P(k+1)이 참임을 보이는 단계
사용 예시
예시 1	모든 자연수 n에 대해 1 + 2 + ... + n = n(n+1)/2 임을 증명
예시 2	모든 자연수 n에 대해 n³ - n은 3의 배수임을 증명
주의 사항
주의 1	기본 단계와 귀납 단계를 모두 증명해야 함
주의 2	귀납 단계에서 P(k)가 참이라는 가정이 필요
관련 개념
관련 개념	수학, 증명, 재귀

2. 정의

페아노 공리계에서 수학적 귀납법은 다음과 같이 정의된다.

임의의 1항 술어 $P(-)$ 가 다음 두 조건을 만족시킨다고 하자.

$P(0)$ 이 성립한다.
임의의 $n\in\mathbb N$ 에 대하여, 만약 $P(n)$ 이 성립한다면, $P(n+1)$ 역시 성립한다.

그렇다면, 임의의

n\in\mathbb N

에 대하여,

P(n)

이 성립한다. 이를 기호로 표기하면 다음과 같다.

:

\forall P(-)((P(0)\land\forall n(P(n)\implies P(n+1)))\implies\forall n P(n))

수학적 귀납법을 구체적으로 서술하면 다음과 같다. 임의의 자연수 부분 집합

S\subseteq\mathbb N

이 다음 두 조건을 만족시킨다고 하자.

$0\in S$
임의의 $n\in\mathbb N$ 에 대하여, $n\in S$ 라면, $n+1\in S$

그렇다면,

S=\mathbb N

이다. (즉, 임의의

n\in\mathbb N

에 대하여,

n\in S

이다.) 이를 기호로 표기하면 다음과 같다.

:

\forall S\subseteq\mathbb N(0\in S\supseteq S+1\implies S=\mathbb N)

2차 논리에서는 다음과 같이 "귀납법의 공리"를 쓸 수 있다.

:

\forall P\,\Bigl( P(0) \land \forall k \bigl( P(k) \to P(k+1)\bigr ) \to \forall n \,\bigl(P(n)\bigr)\Bigr),

여기서

P(\cdot)

는 하나의 자연수를 포함하는 술어에 대한 변수이며,

k

와

n

은 자연수에 대한 변수이다.

1차 논리 ZFC 집합론에서는 술어에 대한 정량화가 허용되지 않지만, 집합에 대한 정량화를 통해 귀납법을 여전히 표현할 수 있다.

:

\forall A \Bigl( 0 \in A \land \forall k \in \N \bigl( k \in A \to (k+1) \in A \bigr) \to \N\subseteq A\Bigr)

A

는 명제를 나타내는 집합으로 읽을 수 있으며, 이 명제가 성립하는 자연수를 포함한다.

수학적 귀납법이 성립함을 수학적 귀납법의 원리라고 하며, 페아노 공리 Ⅴ^[23]가 수학적 귀납법의 원리 그 자체를 나타낸다.

페아노 산술 등의 형식적인 체계에서는 수학적 귀납법을 증명에 사용해도 좋다는 것이 '''공리로서 가정'''되는 것이 보통이다. 즉, 형식적으로는 자연수의 성질로부터 수학적 귀납법의 정당성이 증명될 수 있는 것이 아니라, 거꾸로 자연수의 본질적인 성질을 부여하는 추론 규칙으로서 수학적 귀납법이 가정되는 것이다.

3. 증명

자연수 (즉, 정수 또는 1)를 포함하는 명제가 모든 값에 대해 성립한다고 추론하기 위한 수학적 귀납법은 두 단계로 구성된다.^[20]

# '''기저 사례''' (또는 '''초기 사례'''): 명제가 0 또는 1에 대해 성립함을 증명한다.

# '''귀납적 단계''' (또는 '''귀납적 단계''', 또는 '''단계 사례'''): 모든 n에 대해, 명제가 n에 대해 성립하면 n+1에 대해서도 성립함을 증명한다. 즉, 명제가 임의의 자연수 n에 대해 성립한다고 가정하고, 명제가 n+1에 대해 성립함을 증명한다.

귀납적 단계에서 특정 n에 대해 명제가 성립한다는 가설은 '''귀납적 가설''' 또는 '''귀납적 가정'''이라고 한다. 귀납적 단계를 증명하기 위해, n에 대한 귀납적 가설을 가정하고 이 가정을 사용하여 명제가 n+1에 대해 성립함을 증명한다.

자연수를 0부터 시작하도록 정의하는 저자는 기저 사례에서 그 값을 사용하고, 자연수를 1부터 시작하도록 정의하는 저자는 그 값을 사용한다.

수학적 귀납법이 성립함을 수학적 귀납법의 원리라고 하며, 페아노 공리 Ⅴ^[23]가 수학적 귀납법의 원리 그 자체를 나타낸다.

1차 논리 ZFC 집합론에서는 술어에 대한 정량화가 허용되지 않지만, 집합에 대한 정량화를 통해 귀납법을 여전히 표현할 수 있다.

$\forall A \Bigl( 0 \in A \land \forall k \in \N \bigl( k \in A \to (k+1) \in A \bigr) \to \N\subseteq A\Bigr)$

A는 명제를 나타내는 집합으로 읽을 수 있으며, 이 명제가 성립하는 자연수를 포함한다. 이것은 공리가 아니라 정리이며, 자연수는 페아노의 공리와 유사한 공리에 의해 ZFC 집합론의 언어로 정의된다는 점을 고려해야 한다.

'''2차 논리'''에서는 다음과 같이 "귀납법의 공리"를 쓸 수 있다.

$\forall P\,\Bigl( P(0) \land \forall k \bigl( P(k) \to P(k+1)\bigr ) \to \forall n \,\bigl(P(n)\bigr)\Bigr),$

여기서 P는 하나의 자연수를 포함하는 술어에 대한 변수이며, k와 n은 자연수에 대한 변수이다.

귀납법의 공리는 기본 사례와 귀납 단계로부터 모든 자연수 n에 대해 P(n)이 성립한다고 추론하는 것의 타당성을 주장한다. 공리의 첫 번째 정량자는 개별 숫자 대신 ''술어''에 걸쳐 범위가 지정된다. 이것은 2차 정량자이며, 이는 이 공리가 2차 논리로 표현되었음을 의미한다. 1차 논리에서 산술 귀납법을 공리화하려면 가능한 각 술어에 대해 별도의 공리를 포함하는 공리 체계가 필요하다.

만약, 공리 V를 사용하여 수학적 귀납법을 굳이 증명한다면, 다음과 같이 나타낼 수 있다.

자연수의 집합을 $\mathbb{N}$ 이라 하고, 명제 $P(n)$ 이 성립하는 $n$ 의 집합을 $M$ 이라고 한다.

$M \equiv \{ n \in \mathbb{N} \mid P(n) \}$

(1) 수학적 귀납법의 가정에 의해, $1$ 은 $M$ 의 요소이다.

$1 \in M$

(2) 임의의 자연수 $r$ 을 취한다. $r\in M$ 을 가정하면, $M$ 의 정의에 의해 $P(r)$ 이 성립한다. 이때, 수학적 귀납법의 절차에 의해 $P(r+1)$ 도 성립한다. 다시, $M$ 의 정의에 의해 $r+1\in M$ 이다. 이로써 $\forall r.\,r\in M \Rightarrow r+1 \in M$ 이 증명된 셈이다.

(1) 및 (2)에 의해, 페아노 공리 V에 의해 $\mathbb{N} \subseteq M$ 을 얻는다. 부분 집합의 정의에 의해, 이것은 $\forall n\in\mathbb{N}.\, P(n)$ 임을 의미한다. (증명 끝)

페아노 산술 등의 형식적인 체계에서는 수학적 귀납법을 증명에 사용해도 좋다는 것이 '''공리로서 가정'''되는 것이 보통이다. 즉, 형식적으로는 자연수의 성질로부터 수학적 귀납법의 정당성이 증명될 수 있는 것이 아니라, 거꾸로 자연수의 본질적인 성질을 부여하는 추론 규칙으로서 수학적 귀납법이 가정되는 것이다.

4. 변형

수학적 귀납법은 다양한 형태로 변형될 수 있다. 가장 일반적인 형태는 귀납 단계에서 모든 k에 대해 P(k)가 성립하면 P(k+1)도 성립함을 보이는 것이다. 이를 통해 P(0)에서 P(n)까지 도달하기 위해 이 단계를 n번 반복한다. 이를 "전임자 귀납법"이라고 부르기도 한다.^[10]

계산 복잡도 분야에서는 "접두사 귀납법"이라는 변형이 사용되는데, 귀납 단계에서 모든 k에 대해 P(k)가 성립하면 P(2k)와 P(2k+1)이 모두 성립함을 보이거나, 또는 모든 k에 대해 P(⌊k/2⌋)가 성립하면 P(k)가 성립함을 보인다. 이를 통해 P(0)에서 P(n)까지 도달하기 위해 이 추론을 log₂n번 반복한다. 이는 숫자의 이진 표현에서 앞부분(접두사)을 바탕으로 추론하기 때문에 "접두사 귀납법"이라고 불린다.^[12]

그 외에도 P(⌊√k⌋)가 성립하면 P(k)가 성립함을 보이는 형태의 귀납법도 존재하며, 이는 로그 시간 병렬 계산 연구에 사용되기도 한다.

수학적 귀납법은 n+1 대신 n+2, 2n 등 다른 형태로 변형하여 증명할 수도 있다.

4. 1. 시작점

정수

m\in\mathbb Z

가 주어졌을 때, 다음 두 조건을 만족하는 임의의 정수 부분 집합

S\subseteq\mathbb Z

를 생각해 보자.

$m\in S$
임의의 $n\in\mathbb Z$ 에 대하여, 만약 $n\in S$ 라면, $n+1\in S$

그렇다면,

\{n\in\mathbb Z\colon n\ge m\}\subseteq S

이다. 즉, 임의의

n\in\mathbb Z

(

n\ge m

)에 대하여,

n\in S

이다. 수학적 귀납법은 여기서

m=0,1

인 특수한 경우이다.

이처럼 수학적 귀납법의 시작점은 0 또는 1이 아닌 다른 정수로 설정할 수 있다. 변수

n

이 나타내는 범위는

n \rarr n+1

이라는 연산으로 닫혀 있다면

\{1, 2, ...\}

일 필요는 없으며, 0을 자연수에 포함시키거나, 임의의 정수

m

에 관한

\{m, m+1, ...\}

과 같은 범위도 가능하다.^[1]

4. 2. 역진 귀납법

자연수

m

이 주어졌을 때, 다음 두 조건을 만족하는 임의의 자연수 부분 집합

S

를 생각해보자.

$m \in S$
임의의 $n \in \mathbb N$ 에 대하여, $n+1 \in S$ 이면, $n \in S$ 이다.

그러면,

\{n \in \mathbb N \colon n \le m\} \subseteq S

이다. 즉,

n \le m

인 임의의

n \in \mathbb N

에 대하여,

n \in S

가 성립한다.

이는 m 이하의 모든 자연수에 대해 명제가 성립함을 증명하는 방법이다. 다시 말해, 어떤 명제가 특정 자연수 m에 대해 성립하고, 어떤 자연수 n+1에 대해 성립하면 그 이전 자연수 n에 대해서도 성립한다는 것을 보이는 것이다.

4. 3. 초한 귀납법

정렬 집합의 원소에 대한 명제는 비반사 관계 <를 가지며 무한 감소 사슬을 포함하지 않는 집합으로 일반화할 수 있다. 서수를 나타내는 모든 집합은 잘 정렬되어 있으며, 자연수의 집합도 그 중 하나이다.^[24]

잘 정렬된 집합에 적용되는 초한 귀납법은 단일 단계로 공식화될 수 있다. 각 서수 n에 대해 명제 P(n)이 성립함을 증명하려면:

# 각 서수 n에 대해, P(m)이 모든 m < n에 대해 성립하면, P(n)도 성립함을 보여라.

이러한 형태의 귀납법은 서수의 집합(이는 전순서로 정렬되어 있으며 따라서 잘 정렬된 유형)에 적용될 때, '''초한 귀납법'''이라고 불린다. 이는 집합론, 위상수학 및 기타 분야에서 중요한 증명 기법이다.

초한 귀납법에 의한 증명은 일반적으로 세 가지 경우로 구분한다.

# n이 최소 원소인 경우, 즉 n보다 작은 원소가 없는 경우

# n이 직접적인 선행자를 갖는 경우, 즉 n보다 작은 원소의 집합이 가장 큰 원소를 갖는 경우

# n이 직접적인 선행자를 갖지 않는 경우, 즉 n이 소위 극한 서수인 경우

엄밀히 말해, 초한 귀납법에서 기본 사례를 증명하는 것은 필요하지 않다. 왜냐하면 이는 "P가 모든 n < m에 대해 참이면 P가 m에 대해 참이다"라는 명제의 무의미한 진실 특별한 경우이기 때문이다. 이는 n < m의 반례가 될 수 있는 값이 없기 때문에 무의미하게 참이다. 따라서 특별한 경우는 일반적인 경우의 특별한 경우이다.

자연수 이외의 집합에 대해서도 집합의 원소를 적절하게 순서화함으로써 수학적 귀납법을 적용할 수 있다. 예를 들어 데카르트 곱 N × N 상에 사전식 순서

: (x, y) > (x′, y′)

: : ⇔ (x > x′) 또는 (x = x′ 이고 y > y′)

를 도입함으로써 N × N 상에서도 수학적 귀납법을 사용할 수 있다.

위와 같은 형태로 자연수에 대해 정식화된 수학적 귀납법은, 임의의 정렬 집합에 대해 다음과 같이 일반화할 수 있다. 이 일반화를 '''초한 귀납법'''( '''''')이라고 한다. 수학적 귀납법과는 달리, 서수 전체(유한, 무한)를 대상으로 구축할 수 있다. 임의 농도의 집합은 선택 공리와 동치인 정렬 가능 정리에 의해 정렬 순서를 가진다고 할 수 있으므로, 선택 공리를 포함하는 공리계라면 초한 귀납법은 임의 농도의 집합에 대해 성립한다고 주장할 수 있다.

;초한 귀납법: (A, ≤) 를 정렬 집합으로 하고, P(x) 를 A 위에서 정의된 명제 함수로 한다. 만약 다음 조건이 성립한다면, 임의의 x ∈ A 에 대해 P(x)는 참이다.

;조건: a 를 A 의 임의의 원소로 한다. x < a를 만족하는 A의 모든 원소 x에 대해 P(x) 가 참이라면, P(a)도 참이다.

단, "<"는 a < b ⇔ ( a ≤ b and a ≠ b)로 정의되는 이항 관계로 한다.

A를 전체 집합으로 한다. A의 각 원소 a에 대해 A(a) = { x∈A | x < a }로 하고, A₁ = { x∈A | P(x) }로 한다. 이때, 초한 귀납법의 '''조건'''은 다음과 같다.

:∀a∈A(A(a)⊆A₁⇒a∈A₁)

와 동치이다. 또한, 여집합에 관한 법칙으로부터

:∀a∈A(A(a)∩A₁^c=∅⇒a∈A₁)

와 동치이다. 이러한 조건이 충족된다는 전제 하에, A₁ = A 즉, A₁^c = ∅가 성립함을 보이면 된다.

이제, A₁^c ≠ ∅라고 가정하여 모순을 유도한다. 귀류법의 가정과 정렬 집합의 정의에 따라, min A₁^c = a가 존재한다. 이 a에 대해, 최소 원소의 정의에 따라 A(a)∩A₁^c = ∅가 성립하므로, a ∈ A₁ 또한 성립한다. 그러나, 이는 a ∈ A₁^c라는 사실에 모순된다. (증명 종료)

4. 4. 기타

수학적 귀납법은 다양한 형태로 변형될 수 있다. 예를 들어, 일반적인 수학적 귀납법에서는 n+1에 대해 증명하지만, n+2, 2n 등 다른 형태로 변형하여 증명할 수도 있다.

다음은 그 예시이다.

임의의 자연수 부분 집합 $S\subseteq\mathbb N$ 이 다음 두 조건을 만족시킨다고 하자.
$0,1\in S$
임의의 $n\in\mathbb N$ 에 대하여, 만약 $n\in S$ 라면, $n+2\in S$
또는, 다음 두 조건을 만족시킨다고 하자.
$0\in S$
임의의 $n\in\mathbb N$ 에 대하여, 만약 $n\in S$ 라면, $2n,2n+1\in S$

그렇다면,

S=\mathbb N

이다. 즉, 임의의

n\in\mathbb N

에 대하여,

n\in S

이다.

예를 들어

n \rightarrow n+1

이 아니라

n \rightarrow n+2

로 증명하고, 시작점이

P(2)

이면 모든 양의 짝수에 대해 증명할 수 있다. 변형으로,

P(2)

부터

n \rightarrow n+2

로 양의 짝수를 증명하고,

P(1)

부터

n \rightarrow n+2

로 양의 홀수를 증명하여, 모든 자연수에 대해 성립함을 증명하는 방법도 있다. 이 외에도,

P(0)

부터

n \rightarrow n+1

과

n \rightarrow n-1

을 모두 증명하여, 모든 정수에 대해 성립함을 증명하는 경우도 있다.

5. 성질

수학적 귀납법은 다른 명제들과의 관계를 통해 그 성질을 더 잘 이해할 수 있다.

페아노 공리계에서 수학적 귀납법을 제외하면, 다음 명제들은 서로 동치이다.^[11]

자연수의 정렬성
초한 귀납법
무한 강하법

수학적 귀납법은 이 세 명제를 함의하지만, 역은 성립하지 않는다. 예를 들어, 집합 {0, 0.5, 1, 1.5, ...}과 상수 0, 단항 연산 (-)+1로 이루어진 구조는 자연수의 정렬성, 초한 귀납법, 무한 강하법을 만족시키지만, 수학적 귀납법은 만족시키지 않는다.^[11]

무한 강하법은 피에르 드 페르마가 사용한 방법으로, 어떤 명제가 모든 자연수에 대해 거짓임을 증명하는 데 사용된다. 어떤 자연수 n에 대해 명제가 참이면, 더 작은 자연수에 대해서도 참임을 보여주는 방식으로, 자연수의 무한히 감소하는 수열이 존재하지 않음을 이용하여 귀류법으로 증명한다.

다음 두 명제의 논리곱은 수학적 귀납법과 동치이다.^[20]^[21]^[22]

자연수의 정렬성 (또는 초한 귀납법 또는 무한 강하법)
모든 0이 아닌 자연수는 어떤 자연수 더하기 1이다. ( $\mathbb N\setminus\{0\}\subseteq\mathbb N+1$ )

5. 1. 수학적 귀납법보다 약한 명제

페아노 공리계에서 수학적 귀납법을 제외하면 다음 두 명제가 서로 동치이다.

자연수의 정렬성
초한 귀납법
무한 강하법

수학적 귀납법은 이 세 명제를 함의하지만, 이 세 명제는 수학적 귀납법을 함의하지 않는다. 예를 들어 집합

\{0,0.5,1,1.5,\dots\}

과 상수

0

, 그리고 단항 연산

(-)+1

으로 이루어진 구조는 자연수의 정렬성, 초한 귀납법 및 무한 강하법을 만족시키지만, 수학적 귀납법을 만족시키지 않으므로 페아노 공리계의 모형이 아니다.^[11]

무한 강하법은 피에르 드 페르마가 사용한 수학적 귀납법의 변형이다. 어떤 명제가 모든 자연수에 대해 거짓임을 증명하는 데 사용된다. 어떤 자연수 n에 대해 명제가 참이면, 엄격하게 더 작은 어떤 자연수에 대해서도 참임을 보여주는 것으로 구성된다. 자연수의 무한히 감소하는 수열은 존재하지 않으므로, 이러한 상황은 불가능하며, 따라서 명제가 어떤 n에 대해서도 참일 수 없음을 귀류법으로 증명한다.

5. 2. 수학적 귀납법과 동치인 명제

다음 두 명제의 논리곱은 수학적 귀납법과 동치이다.^[20]^[21]^[22]

자연수의 정렬성 (또는 초한 귀납법 또는 무한 강하법)
$\mathbb N\setminus\{0\}\subseteq\mathbb N+1$ . 즉, 모든 0이 아닌 자연수는 어떤 자연수 더하기 1이다.

6. 예

수학적 귀납법은 어떤 성질이 모든 자연수에 대해 성립함을 증명할 때 사용되는 방법이다. 증명은 보통 두 단계로 이루어진다.

# 기저 단계: 처음 오는 자연수(보통 0 또는 1)에 대해 성질이 성립함을 보인다.

# 귀납 단계: 어떤 자연수 ''n''에 대해 성질이 성립한다고 가정하고, ''n''+1에 대해서도 성립함을 보인다.

이 두 단계가 완료되면, 모든 자연수에 대해 해당 성질이 성립한다는 결론을 내릴 수 있다.

수학적 귀납법은 항등식, 부등식, 기하학 정리 등 다양한 명제를 증명하는 데 활용된다. 예를 들어, 다음과 같은 연속된 자연수의 합 공식을 수학적 귀납법으로 증명할 수 있다.

: $1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$

먼저, ''n''=1일 때 위 공식이 성립함을 쉽게 확인할 수 있다. 그다음, 임의의 자연수 ''k''에 대해 공식이 성립한다고 가정하고, ''k''+1에 대해서도 공식이 성립함을 보이면 증명이 완료된다.

수학적 귀납법의 작동 원리는 도미노 쓰러뜨리기에 비유되기도 한다. 첫 번째 도미노가 쓰러지고, ''k''번째 도미노가 쓰러지면 ''k''+1번째 도미노도 반드시 쓰러진다는 것을 보이면 모든 도미노가 쓰러진다는 것을 증명하는 것과 같은 원리이다.^[12]

6. 1. 홀수의 합 공식

다음은 홀수의 합 공식이다.

:

1+3+5+\cdots+(2n-1)=n^2

이 공식이 임의의 자연수

n

에 대하여 성립한다는 사실을 수학적 귀납법으로 증명할 수 있다.

;1에 대하여 성립

:1에 대한 공식

1=1^2

은 자명하게 성립한다.

;

n

에 대하여 성립한다는 가정 아래,

n+1

에 대하여 성립

:

n

에 대하여 성립한다고 가정하면, 다음이 성립한다.

::

1+3+5+\cdots+(2n-1)=n^2

:양변에

2n+1

를 더하면 다음과 같다.

::

1+3+5+\cdots+(2n-1)+(2(n+1)-1)=n^2+2n+1=(n+1)^2

:따라서,

n+1

에 대하여도 공식이 성립한다.

수학적 귀납법에 따라, 임의의 자연수

n

에 대하여 홀수의 합 공식이 성립한다.

6. 2. 빨간 눈 퍼즐

어떤 섬에 다음과 같은 조건이 주어졌다고 가정한다.

각 섬사람은 빨간 눈 또는 파란 눈을 가진다.
각 섬사람은 자신을 제외한 다른 사람들의 눈 색깔을 안다.
섬사람은 거울을 볼 수 없고, 다른 사람에게 자신의 눈 색깔을 물어볼 수 없다.
자신이 빨간 눈임을 알게 된 섬사람은 그날 밤 섬을 떠나야 한다.
어느 날 아침, 이방인이 섬을 방문하여 섬사람들 중 빨간 눈을 가진 사람이 있다고 말했다.
다음 지식들은 섬사람들 사이에서 공유 지식이다.
모든 구성원의 사고력은 충분히 뛰어나다.
이방인은 정직하다.

이때, 빨간 눈을 가진 섬사람의 수가

n

이라면, 모든 빨간 눈을 가진 사람들은 이방인이 방문한 날로부터

n

번째 밤에 섬을 떠나게 된다. 이는 수학적 귀납법으로 증명할 수 있다. 이방인은 (

n>1

이라면) 모두가 알고 있는 뻔한 사실을 말했지만, 평소와는 다른 특별한 결과를 가져왔다.^[13]

6. 3. 연속된 자연수의 합

수학적 귀납법|수학적 귀납법^한국어을 사용하여 다음 등식이 성립함을 보일 수 있다.

:

0 + 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.

이 명제를

P(n)

이라 하자.

먼저,

P(0)

은 좌변과 우변이 모두 0이므로 성립한다.

다음으로, 임의의 자연수 ''k''에 대해

P(k)

가 성립한다고 가정하고,

P(k+1)

도 성립함을 보이면 된다. 즉,

:

0 + 1 + 2 + \cdots + k = \frac{k(k+1)}{2}

가 성립한다고 가정하고,

:

0 + 1 + 2 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}

가 성립함을 보여야 한다.

P(k)

를 가정하면,

:

0 + 1 + 2 + \cdots + k + (k+1) = (0 + 1 + 2 + \cdots + k) + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}

가 되어

P(k+1)

도 성립한다.

따라서 수학적 귀납법에 의해, 임의의 자연수 ''n''에 대해 명제

P(n)

이 성립한다.

6. 4. 삼각 부등식

7. 역사

플라톤의 파르메니데스는 수학적 귀납법의 초기 형태를 보여주는 예시이며, 유클리드의 소수 무한성 증명과 바스카라 2세의 "순환 방법"(cyclic method^영어)에서도 그 흔적을 찾을 수 있다.^[31]^[32] 알카라지는 이항 정리 등을 증명하기 위해 수학적 귀납법의 한 형태를 사용했다.^[33]

프란체스코 마우롤리코는 1575년 저서 〈Arithmeticorum libri duo〉에서 귀납법에 대한 엄밀한 서술을 처음으로 제시했고, 이를 통해 가장 작은 n개의 홀수를 더하면 n²이 됨을 증명했다. 야코프 베르누이, 블레즈 파스칼, 피에르 드 페르마도 귀납법을 독립적으로 발견했다.^[31]

오거스터스 드 모르간은 1838년에 처음으로 '귀납법'(induction) 또는 '연속 귀납법'(successive induction)이라는 용어를 사용했다.^[35] 리하르트 데데킨트와 주세페 페아노는 1888년과 1889년에 각각 귀납법을 공식화하고 공리화했다. 데데킨트는 ''''라는 모노그래프에서 '완전 귀납법'(Vollständige Induktion)이라는 표현을 사용했다.^[36]^[37] 페아노는 페아노 공리계를 제안하며 귀납법을 공리화했다.

8. 한계 및 주의사항

때로는, $n$ 에 대해 명제가 성립함을 가정하고 $n-1$ 에 대한 명제를 증명하는 것이 더 편리할 수 있다. 그러나 단일 숫자에 대한 명제의 유효성을 증명하는 것만으로는 기본 사례를 확립하기에 충분하지 않다. 대신, 자연수의 무한 부분 집합에 대한 명제를 증명해야 한다. 예를 들어, 오귀스탱 루이 코시는 먼저 정방향(일반) 귀납법을 사용하여 모든 2의 거듭제곱에 대한 산술-기하 평균 부등식을 증명한 다음, 역 귀납법을 사용하여 모든 자연수에 대해 이를 증명했다.^[15]^[16]

수학적 귀납법의 원리를 직관적으로 설명하면 다음과 같다. 먼저 ''P''(1)을 결론짓고, (a), (b)로부터 ''P''(2)를 결론짓고, (c)를 결합하여 ''P''(3)을 결론짓고, (d)를 결합하여 ''P''(4)를 결론짓는 과정을 반복한다. 이 논의에서 ''P''(2)를 결론짓기 위해서는 2단계의 추론, ''P''(3)을 결론짓기 위해서는 3단계의 추론, …, ''P''(100)을 결론짓기 위해서는 100단계의 추론이 필요하다.

따라서 유한 번의 단계로는 유한 개의 ''n''에 대해서만 ''P''(''n'')을 결론지을 수 있으며, "무한히 많은 자연수 모두에 대해 ''P''(''n'')이 성립한다"라는 수학적 귀납법의 결론에 대해 '무한 길이의 증명'이 주어졌다고는 말할 수 없다.

그래서 페아노 산술 등의 형식적인 체계에서는 수학적 귀납법을 증명에 사용해도 좋다는 것이 '''공리로서 가정'''된다. 즉, 형식적으로는 자연수의 성질로부터 수학적 귀납법의 정당성이 증명될 수 있는 것이 아니라, 거꾸로 자연수의 본질적인 성질을 부여하는 추론 규칙으로서 수학적 귀납법이 가정되는 것이다.

수학적 귀납법을 의도적으로 오용한 농담도 있다.^[26]

8. 1. 모든 말은 같은 색이다?

귀납 단계는 모든 값에 대해 증명되어야 한다. 이를 설명하기 위해, 조엘 E. 코헨은 모든 말은 같은 색임을 수학적 귀납법으로 증명하는 것으로 보이는 다음 주장을 제안했다.^[17]

:''기저 사례:'' 말 ''하나''만 있는 집합에서는 색이 하나뿐이다.

:''귀납 단계:'' 귀납적 가설로, n 마리의 말이 있는 모든 집합 내에서는 색이 하나뿐이라고 가정한다. 이제 n+1 마리의 말이 있는 집합을 보자. 1, 2, 3, …, n, n+1로 번호를 매긴다. 집합 {1, 2, 3, …, n}와 {2, 3, 4, …, n+1}을 고려한다. 각 집합은 n 마리의 말로 구성된 집합이므로, 각 집합 내에는 색이 하나뿐이다. 그러나 두 집합은 겹치므로 모든 n+1 마리의 말 사이에도 색이 하나뿐이어야 한다.

기저 사례 n=1은 자명하며, 귀납 단계는 모든 경우 n > 1에서 올바르다. 그러나 귀납 단계에서 사용된 주장은 n+1=2의 경우 틀린데, "두 집합이 겹친다"는 진술이 {1}과 {2}에 대해 거짓이기 때문이다.

8. 2. 대머리 역설

머리카락이 한 올도 없는 사람은 대머리이다. 대머리인 사람에게 머리카락을 한 올 더해도 역시 대머리이다.^[27] 따라서 수학적 귀납법에 의해, 모든 사람은 대머리이다.

물론 이 "증명"에는 이론상의 근본적인 문제점이 있다. 이 "증명"의 문제점은 "대머리"의 정의를 엄밀하게 머리카락이 몇 올 이하인가로 부여할 수 없는 점, 혹은 "대머리"를 정의할 수 있었다고 하더라도, 임의의 "대머리"에 머리카락을 한 올 더했을 때 반드시 "대머리"가 되는 것은 아니라는 점에 있다. 이상과 같은 논법의 기원은 고대 그리스의 철학자 밀레토스의 에우불리데스(en)가 만들었다고 여겨지는 '''대머리 역설''' (Paradox of the Bald Man)^[28]에 기인한다. 이는 사구의 역설의 기원이기도 하다.

전술한 농담에는 다양한 변형이 있지만, 모두 "소량의 증가 정도로는 큰 차이가 없다. 따라서 수학적 귀납법에 의해 많은 양의 증가에도 차이가 없다"는 오류를 이용하고 있다.

참조

_[1] 논문 Mathematical Induction https://www.sfu.ca/~[...] Simon Fraser University
_[2] 웹사이트 Mathematical Induction http://www.math.harv[...] Harvard University 2013-05-02
_[3] 서적 Proving Programs Correct https://archive.org/[...] John Wiley & Sons
_[4] 웹사이트 Mathematical Induction http://www.earlham.e[...] Earlham College 2011-03-26
_[5] 서적 Mathematical Knowledge and the Interplay of Practices https://books.google[...]
_[6] 웹사이트 The Binomial Theorem https://mathcenter.o[...] 2024-12-02
_[7] 문서 Katz (1998), p. 255
_[8] 문서 harvp|Cajori|1918|p=197|ps=: 'The process of reasoning called "Mathematical Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite.'
_[9] 문서 "It is sometimes required to prove a theorem which shall be true whenever a certain quantity ''n'' which it involves shall be an integer or whole number and the method of proof is usually of the following kind. ''1st''. The theorem is proved to be true when ''n'' = 1. ''2ndly''. It is proved that if the theorem is true when ''n'' is a given whole number, it will be true if ''n'' is the next greater integer. Hence the theorem is true universally. … This species of argument may be termed a continued Polysyllogism|sorites''" (Boole c. 1849 Elementary Treatise on Logic not mathematical pp. 40–41 reprinted in Grattan-Guinness, Ivor and Bornet, Gérard (1997), ''George Boole: Selected Manuscripts on Logic and its Philosophy'', Birkhäuser Verlag, Berlin, isbn|3-7643-5456-9)
_[10] 서적 Mathematical Reasoning Pearson
_[11] 서적 A Beginner's Guide to Mathematical Logic Dover
_[12] 서적 Bounded Arithmetic Bibliopolis 1986
_[13] 웹사이트 Proof:Strong induction is equivalent to weak induction https://courses.cs.c[...] 2023-05-04
_[14] 웹사이트 Strong Induction and Well-Ordering https://www.eecs.yor[...] 2023-05-28
_[15] 웹사이트 Forward-Backward Induction {{!}} Brilliant Math & Science Wiki https://brilliant.or[...] 2019-10-23
_[16] 서적 Cours d'analyse de l'École Royale Polytechnique, première partie, Analyse algébrique, http://visualiseur.b[...] Paris 2017-10-14
_[17] 간행물 On the nature of mathematical proof
_[18] 간행물 Are Induction and Well-Ordering Equivalent? 2019-05-06
_[19] 문서 自然数の定義は {{math|0}} を含む流儀とそうでない流儀があるが、ここでは後者を採用した。{{math|''P''(1)}} が成り立つことを示す代わりに{{math|''P''(0)}} が成り立つことを示す。
_[20] 웹사이트 「数学的帰納法」って何でしたっけ－「帰納法」と「演繹法」－ https://www.nli-rese[...]
_[21] 웹사이트 Mathematical Induction Provides A Tool For Proving Large Problems By Proceeding Through The Solution Of Smaller Increments https://www.encyclop[...] 2020-09-08
_[22] 간행물 Origin of the Name "Mathematical Induction" https://www.jstor.or[...] Taylor & Francis, Ltd
_[23] 문서 リンク先のペアノの公理5.は数学的帰納法そのままの形をしているが、そうではなく、本稿で言うところの公理Vは原典に類似した次のような形式のものである:「集合 $M$ が (1) $1\in M$ 、および (2) すべての自然数 $r$ において、 $r\in M \Rightarrow r+1 \in M$ 、を満たすならば $\mathbb{N}\subseteq M$ である。」
_[24] 문서 "{{math|1=''k'' = 1}} のときは、{{mvar|k}} より真に小さい自然数は存在しないので、{{math|''P''(1)}} が真であることを意味する。"
_[25] 서적 Logic, Sets, and Recursion
_[26] 서적 数理と発想創拓社
_[27] 문서 ここでは「髪の毛が少ない人」の意味で「ハゲ」という言葉を用いている。髪の毛の本数が0本である必要はない。
_[28] 웹사이트 Sorites Paradox http://plato.stanfor[...] 2005
_[29] 간행물 Plato: Parmenides 149a7-c3. A Proof by Complete Induction?
_[30] 간행물 Origin of the Name "Mathematical Induction"
_[31] 문서 Cajori (1918), p. 197The process of reasoning called "Mathematicla Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite.
_[32] 논문 참고(EUCLID’S THEOREM ON THE INFINITUDE OFPRIMES: A HISTORICAL SURVEY OF ITS PROOFS(300B.C.–2017)ROMEO MEˇSTROVI ́C https://arxiv.org/ab[...]
_[33] 문서 Katz (1998), p. 255-259. Another important idea introduced by [[al-Karaji]] and continued by [[Ibn Yahyā al-Maghribī al-Samaw'al|al-Samaw'al]] and others was that of an inductive argument for dealing with certain arithmetic sequences.
_[34] 웹사이트 Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji 1999-07
_[35] 문서 De Morgan: Artikel Induction (Mathematics) in: Penny Cyclopædia XII (1838), S. 465–466.
_[36] 서적 'Was sind und was sollen die Zahlen?' http://gdz.sub.uni-g[...] Braunschweig 1888
_[37] 서적 Was sind und was sollen die Zahlen? Vieweg

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com